package 数据结构_树;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node {
    public int val;
    Node left;
    Node right;

    public Node(int x) {
        this.val = x;
    }
}

public class Tree_ReCur {
    public static void main(String[] args) {
        Node head = new Node(1);

        head.left = new Node(2);
        head.right = new Node(3);

        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        preOrderRecur(head);
        System.out.println("\n");
        preOrderRecur_2(head);
        System.out.println("\n");
        midOrderRecur(head);
        System.out.println("\n");
        midOrderRecur_2(head);
        System.out.println("\n");
        postOrderRecur(head);
        System.out.println("\n");
        postOrderRecur_2(head);
        System.out.println("\n");
        recurByLevel(head);

    }

    private static void preOrderRecur(Node head) {
        if (head == null)
            return;
        System.out.print(head.val + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    private static void midOrderRecur(Node head) {
        if (head == null)
            return;
        midOrderRecur(head.left);
        System.out.print(head.val + " ");
        midOrderRecur(head.right);
    }

    private static void postOrderRecur(Node head) {
        if (head == null)
            return;
        postOrderRecur(head.left);
        postOrderRecur(head.right);
        System.out.print(head.val + " ");
    }

    private static void preOrderRecur_2(Node head) {
        Stack<Node> stk = new Stack<>();
        stk.add(head);
        while (!stk.isEmpty()) {
            head = stk.pop();
            System.out.print(head.val + " ");
            if (head.left != null)
                stk.add(head.right);
            if (head.right != null)
                stk.add(head.left);
        }
    }

    private static void midOrderRecur_2(Node head) {
        Stack<Node> stk = new Stack<>();
        while (!stk.isEmpty() || head != null) {
            if (head != null) {
                stk.add(head);
                head = head.left;
            } else {
                head = stk.pop();
                System.out.print(head.val + " ");
                head = head.right;
            }
        }
    }

    private static void postOrderRecur_2(Node head) {
        Stack<Node> stk1 = new Stack<>();
        Stack<Node> stk2 = new Stack<>();
        stk1.add(head);
        while (!stk1.isEmpty()) {
            head = stk1.pop();
            stk2.add(head);
            if (head.left != null)
                stk1.add(head.left);
            if (head.right != null)
                stk1.add(head.right);
        }
        while (!stk2.isEmpty())
            System.out.print(stk2.pop().val + " ");
    }

    private static void recurByLevel(Node head) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            System.out.print(head.val + " ");
            if (head.left != null)
                queue.add(head.left);
            if (head.right != null)
                queue.add(head.right);
        }
    }
}
